Точні методи розв`язання систем лінійних алгебраїчних рівнянь СЛАР

Реферат
на тему:
Точні методи розв'язання систем лінійних алгебраїчних рівнянь (СЛАР)

Введення

Дана лабораторна робота включає в себе два точних методу рішення систем лінійних алгебраїчних рівнянь (СЛАР):
Метод Гаусса.
Метод Холецкого.
Також дана лабораторна робота включає в себе: опис методу, застосування методу для конкретної задачі (аналіз), код програми вирішення перерахованих вище методів на мові програмування Borland C + + Builder 6.
Опис методу:
Метод рішення СЛАР називають точним (прямим), якщо він дозволяє отримати рішення після виконання кінцевого числа елементарних операцій. До прямих методів відносять метод Крамера, метод Гаусса, метод Холецкого та інші. Основним недоліком прямих методів є те, що для знаходження рішення необхідно виконати велику кількість операцій.
Спочатку розглянемо найбільш поширений метод розв'язання СЛАР - метод Гаусса, що складається в послідовному вилученні невідомих.
Нехай дана система рівнянь
(1)
Процес рішення за методом Гауса складається з двох етапів. На першому етапі (прямий хід) система приводиться до східчастого увазі:


де k n, aii 0, i = , АII - головний елемент системи.
На другому етапі (зворотний хід) йде послідовне визначення невідомих з цієї ступеневої системи.
Прямий хід.
Покладемо А11 0, якщо А11 = 0, то першим в системі запишемо рівняння, в якому А11 0.
Розставимо рівняння системи таким чином, щоб коефіцієнт при х1 мав найбільше значення (іншими словами відсортуємо систему за спаданням).
Перетворимо систему, виключивши невідоме х1 у всіх рівняннях, крім першого (використовуючи елементарні перетворення системи). Для цього помножимо обидві частини першого рівняння на і складемо почленно до другого рівняння системи. Потім помножимо обидві частини першого рівняння на і складемо з третім рівнянням системи. Продовжуючи цей процес, отримуємо систему

Тут (I, j = ) - Нові значення коефіцієнтів і правих частин, які виходять після першого кроку.
Аналогічним чином, вважаючи головним елементом 0, виключимо невідоме х2 із усіх рівнянь системи, крім першого і другого, і т.д. Продовжуємо цей процес поки це можливо.
Якщо в процесі приведення системи (1) до ступінчастого вигляду з'являться нульові рішення (рівності виду 0 = 0) їх відкидають. Якщо ж з'явиться рівняння виду 0 = bi, а bi 0, то це говорить про несумісність системи.
Другий етап (зворотний хід) полягає у вирішенні ступеневої системи. В останньому рівнянні цієї системи висловлюємо першого невідоме xk через інші невідомі (xk +1, ..., xn). Потім підставляємо значення xk в передостаннє рівняння системи і висловлюємо xk-1 через (xk +1, ..., xn), потім знаходимо xk-2, ..., x1.
Тепер розглянемо другий точний метод розв'язання СЛАР - метод Холецкого (метод квадратних коренів).
Він застосовується у разі, якщо матриця системи є симетричною і позитивно визначеною. В основі методу лежить алгоритм спеціального LU-розкладання матриці А, де L - нижня трикутна матриця, а U - верхня трикутна матриця (якщо головний мінор не дорівнює 0, то існує розкладання, причому воно єдино).
Розбиття матриці А = на верхню і нижню приміром буде виглядати так
L = і U = .
У результаті перетворень матриця А приводиться до вигляду A = (Де - Транспонована матриця). Якщо розкладання отримано, то рішення системи зводиться до послідовного розв'язування двох систем з трикутними матрицями: і . Для знаходження коефіцієнтів матриці L невідомі коефіцієнти матриці прирівнюють відповідних елементів матриці A. Потім послідовно знаходять необхідні коефіцієнти за формулами:
, i = 2, 3 ,..., m,
, i = 3, 4 ,..., m,
, i = k +1 ,..., m,

Застосування методу до конкретного завдання (аналіз)

Складаючи завдання на мові програмування Borland C + + Builder 6 для реалізації точних методів розв'язання СЛАР я враховував різну кількість рівнянь в системі (розмірність матриці ставив рівним nxn). Але для перевірки результатів використовував рівняння
(Для перевірки рішення методом Гауса) (2) і
(Для перевірки рішення методом Холецкого) (3)
Методи істотно відрізняються один від одного і як описано вище мають різні підходи для вирішення СЛАР. Реалізувавши методи програмним шляхом і зробивши перевірки, я прийшов до висновку, що не всі СЛАР можна вирішити методом Холецкого. Як описано вище метод Холецкого застосовується для розв'язання систем, які є симетричними і позитивно визначеними. У свою чергу методом Гаусса вирішуються практично всі системи. Винятки становлять невироджені матриці, тобто ті матриці, визначник яких не дорівнює 0.

Лістинг програми

# Include "Unit1. H"
/ / ------------------------------------------------ ---------------------------
# Pragma package (smart_init)
# Pragma resource "*. dfm"
TForm1 * Form1;
int n = 0, l = 0;
float r = 0, p = 0;
const x = 100;
float A [x] [x], Ver [x] [x], Nig [x] [x];
float * X;
float * Y;
bool fl1 = false;
/ / ------------------------------------------------ ---------------------------
__fastcall TForm1:: TForm1 (TComponent * Owner)
: TForm (Owner)
{
}
/ / ------------------------------------------------ ---------------------------
void __fastcall TForm1:: ButtonOkClick (TObject * Sender)
{
TryStrToInt (Edit1-> Text, n);
if (n> 1)
{
StringGrid1-> Enabled = true;
StringGrid1-> RowCount = n;
StringGrid1-> ColCount = n +1;
ButtonClear-> Enabled = true;
ButtonOk-> Enabled = false;
StringGrid1-> Color = clWindow;
ButtonGauss-> Enabled = true;
ButtonHolec-> Enabled = true;
X = new float [n];
for (int i = 0; i <n; i + +)
{
for (int j = 0; j <n +1; j + +)
{
A [i] [j] = NULL;
}
X [i] = NULL;
}
}
else
{
ShowMessage ("Число повинно бути дійсного типу!");
}
}
/ / ------------------------------------------------ ---------------------------
void __fastcall TForm1:: ButtonClearClick (TObject * Sender)
{
StringGrid1-> Enabled = false;
StringGrid1-> RowCount = 0;
StringGrid1-> ColCount = 0;
ButtonClear-> Enabled = false;
ButtonOk-> Enabled = true;
StringGrid1-> Color = clBtnFace;
ButtonGauss-> Enabled = false;
}
/ / ------------------------------------------------ ---------------------------
void __fastcall TForm1:: ButtonGaussClick (TObject * Sender)
{
Memo1-> Lines-> Clear ();
for (int i = 0; i <n; i + +)
{
for (int j = 0; j <n +1; j + +)
{
TryStrToFloat (StringGrid1-> Cells [j] [i], A [i] [j]);
}
}
for (int i = 0; i <n; i + +)
{
for (int j = 0; j <n +1; j + +)
{
if (A [i] [j] == NULL)
{
ShowMessage ("Помилка! Є порожні клітинки!");
fl1 = true;
i = n;
break;
}
}
}
Memo1-> Lines-> Add ("Метод Гауса:");
Memo1-> Lines-> Add ("");
if (! fl1) {
Memo1-> Lines-> Add ("Матриця приводиться до ступінчастого вигляду:");
l = 0;
for (int i = 0; i <n; i + +)
{
for (int j = n-1; j> i; j -)
{
if (A [j-1] [l] <A [j] [l])
{
for (int k = 0; k <n +1; k + +)
{
r = A [j] [k];
A [j] [k] = A [j-1] [k];
A [j-1] [k] = r;
}
l = 0;
}
else
{
if (A [j-1] [l] == A [j] [l])
{
l + +;
j + +;
}
if (l == n +1)
{
j -;
l = 0;
}
}
}
}
for (int k = 0; k <n; k + +)
{
for (int i = k; i <n; i + +)
{
r = A [i] [k];
for (int j = k; j <n +1; j + +)
{
A [i] [j] = A [i] [j] / r;
}
}
for (int i = k +1; i <n; i + +)
{
for (int j = k; j <n +1; j + +)
{
A [i] [j] = A [i] [j]-A [k] [j];
}
}
}
X [n-1] = A [n-1] [n] / A [n-1] [n-1];
for (int i = n-2; i> = 0; i -)
{
r = A [i] [n];
for (int j = i +1; j <= n-1; j + +)
r = rA [i] [j] * X [j];
X [i] = r / A [i] [i];
}
String s = "";
for (int i = 0; i <n; i + +)
{
s = "";
for (int j = 0; j <n +1; j + +)
{
s + = FloatToStr (A [i] [j]) + "";
}
Memo1-> Lines-> Add (s);
}
Memo1-> Lines-> Add ("");
Memo1-> Lines-> Add ("Коріння СЛАР рівні:");
for (int i = 0; i <n; i + +)
{
if (X [i]! = NULL)
{
Memo1-> Lines-> Add ("x" + IntToStr (i +1) + "=" + FloatToStr (X [i]));
}
else
{
Memo1-> Lines-> Add ("Ні коренів!");
break;
}
}
}
}
/ / ------------------------------------------------ ---------------------------
void __fastcall TForm1:: ButtonExitClick (TObject * Sender)
{
Close ();
}
/ / ------------------------------------------------ ---------------------------
void __fastcall TForm1:: RadioButton2Click (TObject * Sender)
{
ButtonGauss-> Visible = false;
ButtonHolec-> Visible = true;
}
/ / ------------------------------------------------ ---------------------------
void __fastcall TForm1:: RadioButton1Click (TObject * Sender)
{
ButtonGauss-> Visible = true;
ButtonHolec-> Visible = false;
}
/ / ------------------------------------------------ ---------------------------
void __fastcall TForm1:: ButtonHolecClick (TObject * Sender)
{
Memo1-> Lines-> Clear ();
for (int i = 0; i <n; i + +)
{
for (int j = 0; j <n +1; j + +)
{
TryStrToFloat (StringGrid1-> Cells [j] [i], A [i] [j]);
}
}
for (int i = 0; i <n; i + +)
{
for (int j = 0; j <n +1; j + +)
{
if (A [i] [j] == NULL)
{
ShowMessage ("Помилка! Є порожні клітинки!");
fl1 = true;
i = n;
break;
}
}
}
Memo1-> Lines-> Add ("МЕТОД ХОЛЕЦКОГО:");
Memo1-> Lines-> Add ("");
if (! fl1) {
Y = new float [n];
for (int i = 0; i <n; i + +)
{
Nig [i] [0] = A [i] [0];
Ver [0] [i] = A [0] [i] / Nig [0] [0];
}
for (int i = 0; i <n; i + +)
{
for (int j = 0; j <n; j + +)
{
if (i <j)
{
Nig [i] [j] = 0;
}
if (i> j)
{
Ver [i] [j] = 0;
}
}
}
for (int i = 1; i <n; i + +)
{
Ver [i] [i] = 1;
}
for (int i = 1; i <n; i + +)
{
for (int j = i; j <n; j + +)
{
for (int k = 0; k <i; k + +)
{
p = p + Nig [j] [k] * Ver [k] [i];
}
Nig [j] [i] = A [j] [i]-p;
p = 0;
}
for (int j = i +1; j <n; j + +)
{
for (int k = 0; k <i; k + +)
{
p = p + Nig [i] [k] * Ver [k] [j];
}
Ver [i] [j] = 1/Nig [i] [i] * (A [i] [j]-p);
p = 0;
}
}
for (int i = 0; i <n; i + +)
{
p = 0;
for (int j = 0; j <i; j + +)
{
p = p + Nig [i] [j] * Y [j];
}
Y [i] = (A [i] [n]-p) / Nig [i] [i];
}
for (int i = n-1; i> = 0; i -)
{
p = 0;
for (int j = n-1; j> i; j -)
{
p = p + Ver [i] [j] * X [j];
}
X [i] = (Y [i]-p) / Ver [i] [i];
}
String s = "";
Memo1-> Lines-> Add ("Нижня трикутна матриця:");
for (int i = 0; i <n; i + +)
{
s = "";
for (int j = 0; j <n +1; j + +)
{
s + = FloatToStr (Nig [i] [j]) + "";
}
Memo1-> Lines-> Add (s);
}
Memo1-> Lines-> Add ("Верхня трикутна матриця:");
for (int i = 0; i <n; i + +)
{
s = "";
for (int j = 0; j <n +1; j + +)
{
s + = FloatToStr (Ver [i] [j]) + "";
}
Memo1-> Lines-> Add (s);
}
Memo1-> Lines-> Add ("");
Memo1-> Lines-> Add ("Коріння СЛАР рівні:");
for (int i = 0; i <n; i + +)
{
if (X [i]! = NULL)
{
Memo1-> Lines-> Add ("x" + IntToStr (i +1) + "=" + FloatToStr (X [i]));
}
else
{
Memo1-> Lines-> Add ("Ні коренів!");
break;
}
}
}
}
/ / ------------------------------------------------ ---------------------------
Результати розрахунку:

Метод Гауса:	МЕТОД ХОЛЕЦКОГО:
На першому етапі матриця приводиться до ступінчастого вигляду: 1 - 2,25 0,5 0,5 0 1 6 4 0 0 1 0,625 На другому етапі обчислюються коріння СЛАР виходячи з ступеневої системи: x1 = 0,75 x2 = 0,25 x3 = 0,625	Матриця розбивається на верхню і нижню трикутні матриці. Нижня трикутна матриця: 81 0 0 0 45 24,9999980926514 0 0 45 10,0000019073486 8,99999618530273 0 Верхня трикутна матриця: 1 - 0,555555582046509 0,555555582046509 0 0 1 0,400000095367432 0 0 0 1 0 Коріння СЛАР рівні: x1 = 6 x2 = - 5 x3 = - 4